package linearlist.impl;

import linearlist.Linearlist;
import linearlist.Node;

/**
 * 链表
 * Created by Administrator on 2017/3/9.
 */
public class LinkList<E> implements Linearlist<E> {
    /*指向第一个节点的引用（用于找到链表）*/
    private Node<E> start;
    /*记录当前链表节点的个数*/
    private int size;


    @Override
    public boolean add(E e) {
        /*如果当前链表没有节点，此时添加的节点应该是第一个*/
        /*如果当前链表有节点，则找到最后一个节点*/
        /*1、定义一个空节点指向第一个节点，通过引用指向最后一个节点
          2、将新节点（数据封装）赋值给最后一个节点的next（引用）
         */
        if (size == 0) {
            start = new Node<E>(e);
            size++;
        } else {
            Node<E> node = start;
            while (node.next != null) {
                node = node.next;
            }

            node.next = new Node<E>(e);
            size++;
            return true;
        }
        return false;
    }

    @Override
    public boolean add(E e, int i) {
       /*判断i值
        1、i<0或i>size，错误
        2、i=0，增加到开始位置
        3、0<i<size，插入一个新节点
        4、i=size，增加到最后位置
        */
        Node<E> current;
        Node<E> previous;
        if (i < 0 || i > size) {
            throw new RuntimeException("不存在该位置");
        }
        Node<E> newNode = new Node<E>(e);
        /*插入第一个*/
        if (i == 0) {
            newNode.next = start;
            size++;
        }
        /*两个元素间插入*/
        else {
            current = start;
            previous = null;
            int j = 0;
            while (current != null && j < i) {
                previous = current;
                current = current.next;
                j++;
            }
            if (j == i) {
                previous.next = newNode;
                newNode.next = current;
                size++;
            }
        }
        return true;
    }

    @Override
    public E remove(int i) {
        E oldValue = null;
        if (isEmpty() || i < 0 || i > size - 1) {
            oldValue = null;
        }
        Node<E> current = start;
        if (i == 0) {
            oldValue = current.data;
            start = current.next;
            size--;
        } else {
            Node<E> previous = null;
            int j = 1;
            while (current.next != null && j <= i) {
                previous = current;
                current = current.next;
                j++;
            }
            previous.next = current.next;
            oldValue = current.data;
            current = null;
            size--;
        }
        return oldValue;
    }

    @Override
    public int indexOf(E e) {
        int i = 0;
        if (e == null) {
            for (Node<E> x = start; x != null; x = x.next) {
                if (x.data == null)
                    return i;
                i++;
            }
        } else {
            for (Node<E> x = start; x != null; x = x.next) {
                if (e.equals(x.data))
                    return i;
                i++;
            }
        }

        return -1;
    }

    @Override
    public E get(int i) {
        E e = null;
        if (isEmpty() || i < 0 || i > size - 1) {
            e = null;
        }
        Node<E> current = start;
        int j = 0;
        while (current.next != null && j < i) {
            current = current.next;
            j++;
        }
        if (j == i) {
            e = current.data;
        }
        return e;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
        for (Node<E> x = start; x != null; ) {
            Node<E> next = x.next;
            x.data = null;
            x.next = null;
            x = next;
        }
        start = null;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
